import java.util.Arrays;

/**
 * @program: 1.24 排序
 * @description:
 * @author: 李鑫月
 * @create: 2022-01-24 09:45
 **/
public class TestDemo {
    /**
     * 其实就是一个直接插入排序
     * @param array 待排序序列
     * @param gap 组数
     */
    public static void shell(int[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp=array[i];
            int j = i-gap;
            for (; j >=0 ; j-=gap) {
                if(tmp<array[j]){
                    array[j+gap]=array[j];
                }else{
                    break;
                }
            }
            array[j+gap]=tmp;
        }
    }

    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            shell(array,gap);
            gap /= 2;
        }
        shell(array,1);//保证最后是1组
    }
    /**
     * 选择排序
     * 稳定性：不稳定
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * @param array 待排序序列
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i <array.length ; i++) {
            int j=i+1;
            int minIndex=i;
            for (; j <array.length; j++) {
                if(array[minIndex]>array[j]){
                    minIndex=j;
                }
            }
            int tmp=array[minIndex];
            array[i]=array[minIndex];
            array[minIndex]=array[i];
        }
    }
//    public static void heapSort(int[] array){
//
//    }
    /**
     *
     * @param array1 有序的
     * @param array2 有序的
     * @return
     */
    public static int[] mergeArray(int[] array1,int[] array2) {
        int size=array1.length+array2.length;
          int[] array=new int[size];
          int i=0;
          int j=0;
          int count=0;
          while (i<array1.length&&j<array2.length){
              if (array1[i]<=array2[j]) {
                  array[count++] = array1[i++];

              }else{
                  array[count++] = array2[j++];
              }
              
          }
          if(i!=array1.length){
              while (i<array1.length){
                  array[count++]=array1[i++];
              }
          }else {
              while (j!=array2.length){
                  array[count++]=array2[j++];
              }
          }
             return array;



    }
    public static void main(String[] args) {
        int[] array1={1,3,4,5,8,9};
        int[] array2={2,4,6,8,10};
        int[] ret=mergeArray(array1,array2);
        System.out.println(Arrays.toString(ret));

    }
}
